1. Field of the Invention
This invention relates to dynamic branch prediction mechanisms for microprocessors. More specifically to a branch target buffer wherein the branch prediction entries are divided into sets and each set of branch prediction entries shares a branch pattern table.
2. Art Background
Early microprocessors generally processed instructions one at a time. Each instruction was processed using four sequential stages: instruction fetch, instruction decode, execute, and result writeback. Within such microprocessors, different dedicated logic blocks performed each different processing stage. Each logic block waits until all the previous logic blocks complete operations before beginning its operation.
To improve microprocessor efficiency, microprocessor designers overlapped the operations of the fetch, decode, execute, and writeback stages such that the microprocessor operated on several instructions simultaneously. In operation, the fetch, decode, execute, and writeback stages concurrently process different instructions. At each clock tick the results of each processing stage are passed to the following processing stage. Microprocessors that use the technique of overlapping the fetch, decode, execute, and writeback stages are known as "pipelined" microprocessors.
In order for a pipelined microprocessor to operate efficiently, an instruction fetch unit at the head of the pipeline must continually provide the pipeline with a stream of instructions. However, conditional branch instructions within an instruction stream prevent an instruction fetch unit at the head of a pipeline from fetching the correct instructions until the condition is resolved. Since the condition will not be resolved until further down the pipeline, the instruction fetch unit cannot fetch the proper instructions.
To alleviate this problem, many pipelined microprocessors use branch prediction mechanisms that predict the outcome of branches, and then fetch subsequent instructions according to the branch prediction. To predict the outcome of branch instructions, most branch prediction mechanisms collect branch "histories" that store the outcome of the last K occurrences of each branch.
The Yeh & Patt prediction mechanism dynamically maintains two levels of branch history. The first level of branch history maintained is the branch outcome of the last k occurrences of a particular branch. The first level of branch history is stored in a branch target buffer along with a tag address and a target address. The second level of branch history maintained is the outcome of branches that have a particular branch history pattern provided by the first level. The second level of branch history is stored in a pattern table such that the first level of branch history is used to index into the pattern table.
In the November 1991 paper, Yeh & Patt suggested using a single global pattern table that is used by all the entries in the branch target buffer. Since the single global pattern table is shared by all the entries in the branch target buffer, the different branches create interference. The branch interference tends to reduce the accuracy of the branch predictions.
In a later paper, Yeh & Patt suggested providing a branch pattern table for each branch prediction entry in the branch target buffer. (See Tse Yu Yeh and Yale. N. Patt, Alternative Implementations of Two-Level Adaptive Branch Prediction, Proceedings of the 19th International Symposium on Computer Architecture, May 1992, pp. 124-134) Providing an individual branch pattern table for each branch prediction entry completely removes the pattern table interference and thereby improves the branch prediction accuracy. However providing a branch pattern table for each branch prediction entry in the branch target buffer greatly increases the hardware implementation cost.